googologywikiaorg-20200223-history
User blog:P進大好きbot/Full References of Arguments on Ordinal Notations with Large Cardinals
I would like to list up references of the proof of statements on which the well-definedness of ordinal notations with large cardinals under \(\textrm{ZFC}\). If you know precise references which I have not mention, please inform me. I think that listing up full references helps us to prove the well-definedness of given ordinal notations and the correctness of analyses of them. For example, if a table of analysis contains an ordinal whose well-definedness actually depends on axioms indepedent of \(\textrm{ZFC}\), the analysis will be turned to be incorrect. There might be googologists working on fixed stronger axioms than \(\textrm{ZFC}\), e.g. \(\textrm{ZFC} + \textrm{Inaccessible}\). It is great that we have googology under each choice of reasnable axioms. On the other hand, if you do not fix axioms, i.e. assume any additional axioms compatible with your analysis, then this blog is not worth reading. Your analysis is always correct under the strongest axiom \(0 = 1\) or the weaker axiom directly stating that your analysis is correct. Anyway, I would like to know which axioms analysts here are using in their analysis. To begin with, I asked three analysist here. * Alemagno12: No specific axiom.'He said "I don't use any specific choice of axioms when analyzing and I haven't ever used any. I have tried to do ordinal analysis of \(\textrm{Z}_2\) though (although I didn't make much progress and eventually gave up on it), and I might try doing an analysis using \(\textrm{ZFC}\) in the future." The siurce is here. * KurohaKafka: '''Essentially no specific axiom.'He said "I am conscious of no asumption of axioms. So to speak, I guess that I am assuming axioms which ensure the existence of each natural number and also assuming the defining system of a target large number itself, as long as the computation terminates. Another aspect is that I intend to analyse what model of computation the defining system corresponds to. Something like the asserion that Primitive Sequence System corresponds to simply typed \(\lambda\)-calculus, for example?" The source is here. * rpakr: '''I am waiting for the answer. * Emlightened: \(\textrm{ZFC}\) and other reasonable axioms which are obviously necessary in the context.'''The source is here So they mainly do not use large cardinal axioms, or even \(\textrm{ZFC}\). Then the analysis would be done by pointwise comparison for finite examples by hand, and the termination would never be provable. If we assumme no axiom other than logical axioms, then we can prove nothing non-trivial. Namely, it is impossible to prove the well-definedness of the smallest infinite ordinal \(\omega\), or even the well-definedness of the addition given by the recursion of the successor. I guess that they accept the well-definedness of such basic notions, and hence they would implicitly assume several axioms. A problem will occur when they are unaware of use of large cardinal axioms. A statement which is provable under large cardinal axioms is not necessarily provable under \(\textrm{ZFC}\). Even if we assume the consistency of \(\textrm{ZFC}\), it is impossible to prove the consistency of large cardinal axioms, and we have a model of set theory on which large cardinal axioms are false. Please inform me of what axioms you use in your analysis, if you are another analysist here. = Introduction = Before reading this blog post, it is better to understand common mistakes on use of large cardinals in googology under \(\textrm{ZFC}\), which I wrote in a previous blog post. Also, the arguments in the replies of my another blog post might be worth reading. Since it is well-known that the topic of large cardinals is absolutely difficult to understand, googologists would always be careful about such arguments. Nevertheless, why such mistakes occurs? Here is one of the answers. There are several sophisticated articles and blog posts on ordinal notations with large cardinals and analyses of them, but the blog posters do not necessarily quote full references of the original paper. Then many googologists refer to large cardinals without knowing original statements or original proofs. Without full references, googologists might comfound blog poster's personal descriptions and original arguments. This is the reason. Also, omitting the full references is awfully problematic by several aspects: * '''It ignores the authority of the original paper. * It hides the responsibility of personal descriptions. * It prevents us from confirming that a given argument has already been reviewed or not. One of the worst problem is that googologists regard wrong assertions by blog posters as statements verified by the authors of the original papers. Although it is impossible to thoroughly annihilate all such troubles, it is much better to know the full reference of each statement. I emphasise that I might write incorrect arguments here. Please point out 'explicitly' if there are some errors. = References = # Buc W. Buchholz, [http://www.mathematik.uni-muenchen.de/~buchholz/articles/M1.pdf A Note on the Ordinal Analysis of KPM], a note. # KPM M. Rathjen, Provable wellorderings of KPM, in preparation. # KPM2 M. Rathjen, [https://link.springer.com/article/10.1007/BF01275469 Collapsing functions based on recursively large ordinals: A well-ordering proof for KPM], Archive for Mathematical Logic, Volume 33, pp. 35--55, 1994. # Lav R. Laver, On the Algebra of Elementary Embeddings of a Rank into Inself, a preprint in arXiv. # PT K. Schutte, [https://link.springer.com/book/10.1007%2F978-3-642-66473-1 Proof Theory], Part of the Grundlehren der mathematischen Wissenschaften book series, Volume 225, Springer-Verlag, 1977. # Dou R. Dougherty, Critical Points in an Algebra of Elementary Embeddings, a preprint in arXiv. # WM M. Rathjen, [https://link.springer.com/article/10.1007/BF01651328 Ordinal notations based on a weakly Mahlo cardinal], Archive for Mathematical Logic, Volume 29, Issue 4, pp. 249--263, 1990. # WI M. Rathjen, [https://link.springer.com/article/10.1007/BF01621475 Proof-theoretic analysis of KPM], Archive for Mathematical Logic, Volume 30, Issue 5--6, pp. 377--403, 1991. # WC M. Rathjen, [https://www.sciencedirect.com/science/article/pii/0168007294900744 Proof Theory of Reflection], Annals of Pure and Applied Logic, Volume 68, Issue 2, pp. 181--224, 1994. = Weakly Mahlo Cardinal = This topic is mainly written in WM. Convention * Following the convention in WM, \(M\) denotes the smallest weakly Mahlo cardinal. * I abbreviate "the existence of a weakly Mahlo cardinal" to \(\exists M\). Definition of the Ordinal Notation System (T(M),<) Safe! It is defined just under \(\textrm{ZFC} + \exists M\) in Section 6 in WM, but it will be translated into a system under \(\textrm{ZFC}\) in Section 7 in WM. Primitive Recursiveness of (T(M),<) Safe! It is verified under \(\textrm{ZFC}\) in Section 7 by applying Lemma 2.2 (vi), Proposition 2.4, Corollary 3.14, Lemma 5.5 (v) and (vi), Proposition 5.10, Lemma 5.13, and Lemma 5.14, Lemma 7.2, and Lemma 7.5 in WM. Well-foundedness of (T(M),<) Dangerous? It is verified just under \(\textrm{ZFC} + \exists M\) in Section 7 in WM. Rathjen wrote that it could be proved under \(\textrm{ZFC}\) by replacing \(M\) by its recursve analogue, and would be actually proved in a forthcoming paper. But I do not know in which paper Rathjen actually proved it. Also, if the well-foundedness is not proved, then the well-definedness of the ordinal notation with weakly inaccessible cardinals is unknown because the proof of the well-definedness of the correspondence from ordinal terms to ordinals heavily uses the transfinite induction, which obvously depends on the well-foundedness. I note that several googologists here state that it is well-defined, and use the ordinal notation with weakly inaccessibles in their analyses. Therefore this just means that I lack knowledge. At least, when I asked a professional of proof theory, he said that it is perhaps unpublished. Please tell me a reference of the proof. Definition of ψ_{Ω_1}(ε_{M+1}) and Relation to KPM Dangerous? I am Sorry, but I do not know the precise reference of the equality \(\textrm{PTO}(\textrm{KPM}) = \psi_{\Omega_1}(\varepsilon_{M+1})\). I just know this by the list here in googology wiki and Corollary in p. 8 in Buc states \(\textrm{PTO}(\textrm{KPM}) \leq \psi_{\Omega_1}(\varepsilon_{M+1})\). Maybe the equality is verified in an unpublished result. When I asked a professional of proof theory, he told me that it seems to be unpublished and there are many forklores which are not explicitly written. On the other hand, Deedlit11 states that the proof has already been published'''A source is here. In WI, which Deedlit11 mentioned, Rathjen just stated a related equality and wrote that the proof was written in an unpublished note. So it is mysterious. Is there someone published Rathjen's unpublished note? Or is there a proof in WI which is visible only for honest people? Although I pointed out the fact, he has not corrected his statement or his blaming me as pedantic one. '''Please tell me a reference of the proof. Since \(\varepsilon_{M+1}\) does not make sense under \(\textrm{ZFC}\), the equality \(\textrm{PTO}(\textrm{KPM}) = \psi_{\Omega_1}(\varepsilon_{M+1})\) is not provable under \(\textrm{ZFC}\). You can regard \(\psi_{\Omega_1}(\varepsilon_{M+1})\) as a syntax sugar of \(\textrm{PTO}(\textrm{KPM})\) under \(\textrm{ZFC}\), but then you need to be very careful that properties on \(\psi\) are not applicable to \(\textrm{PTO}(\textrm{KPM})\) any more. Definition of ψ_{Ω_1}(ψ_{χ_{ε_{M+1}}(0)}(0))) and Relation to KPM Safe! Here, I consider the equality \(\textrm{PTO}(\textrm{KPM}) = \psi_{\Omega_1}(\psi_{\chi_{\varepsilon_{M+1}}(0)}(0))\) under \(\textrm{ZFC} + \exists M\). If it is true, then \(\psi_{\Omega_1}(\psi_{\chi_{\varepsilon_{M+1}}(0)}(0))\) can be regarded as a syntax sugar of \(\textrm{PTO}(\textrm{KPM})\) under \(\textrm{ZFC}\). The inequaility \(\textrm{PTO}(\textrm{KPM}) \leq \psi_{\Omega_1}(\psi_{\chi_{\varepsilon_{M+1}}(0)}(0))\) is verified under \(\textrm{ZFC} + \exists M\) in Theorem 7.14 (iii) in WI. On the other hand, the opposite inequality \(\textrm{PTO}(\textrm{KPM}) \geq \psi_{\Omega_1}(\psi_{\chi_{\varepsilon_{M+1}}(0)}(0))\) is just stated in Theorem 7.15 in WI. Rathjen wrote that it follows from his preprint KPM, but it seems unpublished or even not open. Instead, Rathjen verified the opposite inequality Corollary 5.8 in the other paper KPM2. Therefore the equality has already been verified. On the other hand, as I wrote above, Deedlit11 states that a proof of the theorem is written in WI. So please ask him where to read a proof in WI if you do not mind being blamed as pedantic one. = Weakly Inaccessible Cardinal = This topic is mainly written in WI. I note that the function \(\psi\) appear in WI is a variant of (and actually different from) the original one defined in WM. Convention * Following the convention in WM, \(\chi\) denotes the \(2\)-variable enumeration function of limits of higher inaccessible cardinals. * I denote by \(M\) the smallest weakly Mahlo cardinal, and abbreviate "the existence of a weakly Mahlo cardinal" to \(\exists M\). * I abbreviare \(\chi_1(0)\) to \(I\). I note that \(M\) denotes a constant term symbol in WI, and hence my convention here is different from the original one. Definition of the Ordinal Notation System (T(M),<) Safe! It is defined under \(\textrm{ZFC}\) in Section 2 in WI. Unlike the ordinal notation system \((\textrm{T}(M),<)\) with a weakly Mahlo cardinal in WM, the symbol \(M\) is directly used in the system as a constant term symbol but not as the smallest weakly Mahlo cardinal. Primitive Recursiveness of (T(M),<) Safe! It is verified under \(\textrm{ZFC}\) in Theorem 2.8 (i) in WI by the constructive means in Theorem 14.2 in KPM. Well-foundedness of (T(M),<) Dangerous? It is verified just under \(\textrm{ZFC}\) plus the well-foundedness of the ordinal notation system with \(M\) in Theorem 2.8 (ii) in WI. As I mentioned above, I could not find a proof of the well-foundedness of the ordinal notation system with \(M\) under \(\textrm{ZFC}\). If it is just proved under \(\textrm{ZFC} + \exists M\), then the well-definedness of the ordinal notation with weakly inaccessible cardinals is 'NOT' verified. I note that several googologists here state that it is well-defined, and use the ordinal notation with weakly inaccessibles in their analyses. Therefore this just means that I lack knowledge. Please tell me a reference of the proof. Definition of the OCF ψ_I Partially Safe! It is originally defined as a function symbol in \(\textrm{ZFC}\) in the Section 2 in WI. Therefore in order to regard it as an OCF, we need to transfer the ordinal notation system to a set of ordinals. Then we need \(\textrm{ZFC} + \exists M\) by the last subsection. On the other hand, \(\psi_I(0)\) coincides with the omega fixed point under \(\textrm{ZFC} + \exists M\). Therefore \(\psi_I(0)\) makes sense under \(\textrm{ZFC}\) as a syntax sugar of the omega fixed point. Similarly, \(\psi_I\) might be regarded as a syntax sugar of the enumertion function of the function \(\textrm{ON} \to \textrm{ON}, \ \alpha \mapsto \Omega_{\alpha}\) in googology wiki, and hence makes sense under \(\textrm{ZFC}\). However, a problem occurs if you use any property of real \(\psi_I\) based on the well-foundedness. Definition of ψ(ψ_I(0)) and Relation to Π_1^1-TR_0 Safe? I am Sorry, but I do not know the precise reference of the equality \(\textrm{PTO}(\Pi_1^1-\textrm{TR}_0) = \psi(\psi_I(0))\). I just know this by the list here in googology wiki. Since the article says that the \(\psi\) is an OCF, it does not literally coincide with the function symbol \(\psi\) in WI. Anyway, since \(\psi_I(0)\) makes sense under \(\textrm{ZFC}\) as I mentioned above, the equality \(\textrm{PTO}(\Pi_1^1-\textrm{TR}_0) = \psi(\psi_I(0))\) would be provable under \(\textrm{ZFC}\) if we ignore the explanation in the article that \(\psi\) is an OCF and regard the right hand side as the ordinal type of the corresponding expression in \((T(M),<)\). Please tell me a reference of the proof. Definition of ψ_{Ω_1}(ε_{I+1}) and Relation to KPI Dangerous? I am Sorry, but I do not know the precise reference of the equality \(\textrm{PTO}(\textrm{KPI}) = \psi_{\Omega_1}(\varepsilon_{I+1})\). I just know this by the list here in googology wiki. Since \(\varepsilon_{I+1}\) does not make sense under \(\textrm{ZFC}\), the equality \(\textrm{PTO}(\textrm{KPI}) = \psi_{\Omega_1}(\varepsilon_{I+1})\) is not provable under \(\textrm{ZFC}\). You can regard \(\psi_{\Omega_1}(\varepsilon_{I+1})\) as a syntax sugar of \(\textrm{PTO}(\textrm{KPI})\) under \(\textrm{ZFC}\), but then you need to be very careful that properties on \(\psi\) are not applicable to \(\textrm{PTO}(\textrm{KPI})\) any more. Please tell me a reference of the proof. = Weakly Compact Cardinal = This topic is mainly written in WC. WIP = Huge Cardinal = WIP = Stage Cardinal = It is ill-defined. See this. = Rank-in-Rank Cardinal = The existence of Rank-in-Rank cardinal is used to verify the totality of a fast growing function \(q\) defined by using Laver's table introduced in Lav. The function \(q\) is believed to grow very fast, and only the lower bound is known under that axiom. For the estimation of lower bounds, see Dou. = UNOCF = UNOCF is one of a famous OCF or notation system widely used in this community. It uses a placeholder which looks like symbols of large cardinals. On the other hand, UNOCF is just known by expansion rules for finitely many ordinals, and hence has not been formalised yet. Therefore it has not be verified that such symbols actually behaves as large cardinals in standard OCFs. Namely, it is not known that the weakly Mahlo (resp. weakly compact) level with respect to UNOCF is actually near the weakly Mahlo (weakly compact) level with respect to standard OCFs. So formalising the definition of UNOCF and verifying its strength are ones of open and significant topic. For the issues, see this. = Footnotes = Category:Blog posts